typedef struct {
    int top;
    char *sym;
}stack_t;

void stack_init(stack_t **s, int size) {
    *s = malloc(sizeof(stack_t));
    (*s)->top = -1;
    (*s)->sym = malloc(sizeof(char) * size);    
}

int is_empty(stack_t *s) {
    return (s->top == -1);
}
char pop(stack_t *s) {
    return s->sym[s->top--];
}
void push(stack_t *s, char ch) {
    s->sym[++s->top] = ch;
}
char top(stack_t *s) {
    return s->sym[s->top];
}
bool isValid(char * s){
    int i, len = strlen(s);
    stack_t *stack;
    stack_init(&stack, len);

    for (i = 0; i < len; i++) {
        if (s[i] == '[' || s[i] == '(' || s[i] == '{')
            push(stack, s[i]);
        else {
            if (is_empty(stack)) return false;
            char ch = top(stack);
            if (ch == '[' && s[i] == ']') pop(stack);
            else if (ch == '{' && s[i] == '}') pop(stack);
            else if (ch == '(' && s[i] == ')') pop(stack);
            else return false;
        }
    }
    if (is_empty(stack)) return true;
    else return false;
}